#include"Sort.h"

int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	Swap(&a[midi], a[begin]);
	int prev = begin;
	int cur = prev + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi])
		{
			++prev;
			if (prev != cur)
			{
				Swap(&a[prev], &a[cur]);
			}
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	return prev;
}